package com.ocean.linkedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/linked-list-cycle-ii/
 */
public class LinkedListCycleDetect {
    public static void main(String[] args) {

        ListNode e5 = new ListNode(5, null);
        ListNode e4 = new ListNode(4, e5);
        ListNode e3 = new ListNode(3, e4);
        ListNode e2 = new ListNode(2, e3);
        ListNode e1 = new ListNode(1, e2);
        e5.next = e5;
        ListNode listNode = new LinkedListCycleDetect().detectCycle(e1);
        System.out.println(listNode);
    }


    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;

        while (true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 到这里说明相遇了
        ListNode third = head;
        while (third != slow) {
            slow = slow.next;
            third = third.next;
        }
        return third;
    }
}
